from typing import List


class Solution:
    def maximumInvitations(self, grid: List[List[int]]) -> int:
        def match(i):
            """第i个男孩是否能找到女孩"""
            for j in range(n):
                if grid[i][j] == 1 and j not in visited:  # 只要是没尝试过的就尝试一下
                    visited.add(j)  # 标注正在尝试，让已与之匹配的男孩必须改选
                    if j not in girl2boy or match(girl2boy[j]):  # 如果该女孩还没有匹配，或者匹配了但与之匹配的男孩可以改选
                        girl2boy[j] = i  # 与女孩j匹配的男孩是i
                        return True  # 匹配成功返回
            return False  # 遍历所有女孩都没能找到匹配的，匹配失败

        m, n = len(grid), len(grid[0])
        ans = 0

        girl2boy = {}  # 女孩对应的男孩
        for i in range(m):  # 遍历每一个男孩
            visited = set()  # 记录该男孩尝试匹配的女孩
            if match(i):  # 如果男孩能找到匹配的女孩
                ans += 1
        return ans


if __name__ == "__main__":
    # 3
    print(Solution().maximumInvitations(grid=[[1, 1, 1],
                                              [1, 0, 1],
                                              [0, 0, 1]]))

    # 3
    print(Solution().maximumInvitations(grid=[[1, 0, 1, 0],
                                              [1, 0, 0, 0],
                                              [0, 0, 1, 0],
                                              [1, 1, 1, 0]]))
